#include <iostream>
#include <vector>
using namespace std;

/**
 * @方法: dfs
 * @时间复杂度: o(r*c)
 * @空间复杂度: o(r*c)
 * @评价:
 */
int dfs(vector<vector<int>>& mygrid, int r, int c) {
    if (!(0 <= r && r < mygrid.size() && 0 <= c && c < mygrid[0].size())) {
        return 0;
    }
    if (mygrid[r][c] == 0 || mygrid[r][c] == 2) {
        return 0;
    }
    mygrid[r][c] = 2;
    int cnt = !(mygrid[r - 1][c] == 1 || mygrid[r - 1][c] == 2) +
              !(mygrid[r + 1][c] == 1 || mygrid[r + 1][c] == 2) +
              !(mygrid[r][c - 1] == 1 || mygrid[r][c - 1] == 2) +
              !(mygrid[r][c + 1] == 1 || mygrid[r][c + 1] == 2);
    return cnt + dfs(mygrid, r - 1, c) + dfs(mygrid, r + 1, c) +
           dfs(mygrid, r, c - 1) + dfs(mygrid, r, c + 1);
}
int islandPerimeter(vector<vector<int>>& grid) {
    vector<vector<int>> mygrid;
    vector<int> hh;
    for (int i = 0; i < grid[0].size() + 2; i++)
        hh.push_back(0);
    for (int i = 0; i < grid.size() + 2; i++)
        mygrid.push_back(hh);
    for (int row = 0; row < grid.size(); row++) {
        for (int col = 0; col < grid[0].size(); col++) {
            mygrid[row + 1][col + 1] = grid[row][col];
        }
    }

    for (int r = 0; r < mygrid.size(); r++) {
        for (int c = 0; c < mygrid[0].size(); c++) {
            if (mygrid[r][c] == 1) {
                return dfs(mygrid, r, c);
            }
        }
    }
    return 0;
}

/**
 * @方法: 自己的方法，开一个更大的二维数组，遍历二维数组
 * @时间复杂度: o(r*c)
 * @空间复杂度: o(r*c)
 * @评价:
 */
int islandPerimeter1(vector<vector<int>>& grid) {
    int ans = 0;
    vector<vector<int>> mygrid;
    vector<int> hh;
    for (int i = 0; i < grid[0].size() + 2; i++)
        hh.push_back(0);
    for (int i = 0; i < grid.size() + 2; i++)
        mygrid.push_back(hh);
    for (int row = 0; row < grid.size(); row++) {
        for (int col = 0; col < grid[0].size(); col++) {
            mygrid[row + 1][col + 1] = grid[row][col];
        }
    }

    for (int row = 1; row < mygrid.size() - 1; row++) {
        for (int col = 1; col < mygrid[0].size() - 1; col++) {
            if (mygrid[row][col] == 1) {
                ans = ans + !(mygrid[row - 1][col] == 1) +
                      !(mygrid[row + 1][col] == 1) +
                      !(mygrid[row][col - 1] == 1) +
                      !(mygrid[row][col + 1] == 1);
            }
        }
    }
    return ans;
}

int main() {
    cout << "hello world" << endl;
    vector<vector<int>> grid;
    grid.push_back({0, 1, 0, 0});
    grid.push_back({1, 1, 1, 0});
    grid.push_back({0, 1, 0, 0});
    grid.push_back({1, 1, 0, 0});

    cout << islandPerimeter(grid) << endl;
    return 0;
}